#pragma once
#include <vector>
#include <map>
#include <cmath>
using namespace std;
// template <class T>
// class UnionFindSet
// {
// public:
//     UnionFindSet(const T *a, size_t n)
//     {
//         for (size_t i = 0; i < n; i++)
//         {
//             _a.push_back(a[i]);
//             _IndexMap[a[i]] = i;
//         }
//     }

// private:
//     vector<T> _a;          // 编号找人
//     map<T, int> _IndexMap; // 人找编号
// };
class UnionFindSet
{
public:
    UnionFindSet(size_t n) : _ufs(n, -1) {}
    void Union(int x1, int x2)
    {
        int p1 = FindRoot(x1);
        int p2 = FindRoot(x2);
        if (p1 == p2)
            return;
        if (abs(_ufs[p1]) < abs(_ufs[p2]))
        {
            swap(p1, p2);
        }

        _ufs[p1] += _ufs[p2];
        _ufs[p2] = p1;
    }
    int FindRoot(int x)
    {
        int root = x;
        while (_ufs[root] >= 0)
        {
            root = _ufs[root];
        }
        while (_ufs[x] >= 0)
        {
            int tmp = _ufs[x];
            _ufs[x] = root;
            x = tmp;
        }
        return root;
    }
    bool IsInSet(int x1, int x2)
    {
        int p1 = FindRoot(x1);
        int p2 = FindRoot(x2);
        return p1 == p2;
    }
    size_t SetSize()
    {
        size_t size = 0;
        for (auto e : _ufs)
        {
            if (e < 0)
                size++;
        }
        return size;
    }

private:
    vector<int> _ufs;
};

void TestUnionSet()
{
    UnionFindSet ufs(10);
    ufs.Union(9, 8);
    ufs.Union(7, 6);
    ufs.Union(2, 1);
    ufs.Union(3, 4);
    ufs.Union(9, 8);
}